<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

</body>
<script>
    //    二叉树
    function BinarySearchTree() {
        var Node = function (key) { //{1}
            this.key = key;
            this.left = null;
            this.right = null;
        };
        var root = null; //{2}
        this.insert = function (key) {
            var newNode = new Node(key); //{1}
            if (root === null) { //{2}
                root = newNode;
                console.log(root)
            } else {
                insertNode(root, newNode); //{3}
            }
        };
        var insertNode = function (node, newNode) {
            if (newNode.key < node.key) { //{4}
                if (node.left === null) { //{5}
                    node.left = newNode; //{6}
                } else {
                    insertNode(node.left, newNode); //{7}
                }
            } else {
                if (node.right === null) { //{8}
                    node.right = newNode; //{9}
                } else {
                    insertNode(node.right, newNode); //{10}
                }
            }
        };
        // 中序遍历(按照从小到大的顺序遍历  )
        this.inOrderTraverse = function(callback) {
            inOrderTraverseNode(root, callback)
        }
        var inOrderTraverseNode = function(node, callback) {
            // 检查参数传入的节点是否是 null 
            if (node !== null) {
                inOrderTraverseNode(node.left, callback)
                callback(node.key)
                inOrderTraverseNode(node.right, callback)
            }
        }
        
        // 先序遍历(打印一个结构化文档)
        this.perOrderTraverse = function(callback) {
            perOrderTraverseNode(root, callback)
        }
        var perOrderTraverseNode = function(node, callback) {
            if (node !== null) {
                printNode(node.key)
                perOrderTraverseNode(node.left, callback)
                perOrderTraverseNode(node.right, callback)
            }

        }

        // 后序遍历(计算一个目录和他的子目录中所有文件所占空间大小)
        this.postOrderTraverse = callback => {
            postOrderTraverseNode(root, callback)
        }
        var postOrderTraverseNode = (node, callback) => {
            if (node !== null) {
                postOrderTraverseNode(node.left, callback)
                postOrderTraverseNode(node.right, callback)
                printNode(node.key)
            }
        }
        
        // 搜索一个特定的值
        this.search = function(key) {
            return searchNode(root, key)
        }

        var searchNode = function(node, key) {
            if (node === null) {
                return false
            }
            if (key < node.key) {
                return searchNode(node.left, key)
            } else if (key > node.key) {
                return searchNode(node.right, key)
            } else {
                return true
            }
        }
    }
    function printNode(values) {
        console.log(values)
    }
    var tree = new BinarySearchTree();
    tree.insert(11);
    tree.insert(7);
    tree.insert(15);
    tree.insert(5);
    tree.insert(3);
    tree.insert(9);
    tree.insert(8);
    tree.insert(10);
    tree.insert(13);
    tree.insert(12);
    tree.insert(14);
    tree.insert(20);
    tree.insert(18);
    tree.insert(25);
    tree.insert(6);
    // tree.inOrderTraverse(printNode)
    // tree.perOrderTraverse(printNode)
    // tree.postOrderTraverse(printNode)
    console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.');
    console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.');
</script>

</html>